package com.leetcode.partition13;

/**
 * @author rkc
 * @date 2022/8/21 8:44
 */
public class LC1224最大相等频率 {

    private static final int N = 100010;
    //cnt[i]=j表示数值i出现的次数为j，sum[i]=j表示出现次数为i的数值有j种
    private int[] cnt = new int[N], sum = new int[N];

    public int maxEqualFreq(int[] nums) {
        int maxc = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = ++cnt[nums[i]], len = i + 1;
            sum[cur]++;
            sum[cur - 1]--;
            maxc = Math.max(maxc, cur);
            if (maxc == 1) ans = len;
            else if (maxc * sum[maxc] + 1 == len) ans = len;
            else if ((maxc - 1) * (sum[maxc - 1] + 1) + 1 == len) ans = len;
        }
        return ans;
    }
}
